
// 10.正则表达式
class Solution {
public:
    bool isMatch(string s, string p) {
        // 使用动态规划来实现
        int n = s.size() , m = p.size();
        vector<vector<bool>> dp(n + 1 , vector<bool>(m + 1));
        s = " " + s, p = " " + p; 
        dp[0][0] = true;
        for(int i = 2 ; i <= m ; i+=2)   //s是空串
            if(p[i] == '*') dp[0][i] = true;
            else break;
            
        // 进行动态规划
        for(int i = 1; i <= n ; i++)
        {
            for(int j = 1 ; j <= m ; j++)
            {
                if(s[i] == p[j] || p[j] == '.') dp[i][j] = dp[i - 1][j - 1];
                else if(p[j] == '*') 
                {
                    int prev = j - 1;
                    if(p[prev] == '.' || p[prev] == s[i]) dp[i][j] = dp[i - 1][j] || dp[i][j - 2];
                    else dp[i][j] = dp[i][j - 2];
                }
            }
        }            
        return dp[n][m];
    }
};